#include <iostream>
#include <benchmark/benchmark.h>
#define FIBTIME 30

using namespace std;

// Tabulation
long fib(int n, long& prev) {
    if (n == 0)
        {prev = 1; return 0;}
    else {
        long prevPrev;
        prev = fib(n - 1, prevPrev);
        return prevPrev + prev;
    }
}

static void fib_tab(benchmark::State& state) {
    for (auto _: state) {
        long result, prev;
        result = fib(FIBTIME, prev);
    }
}
BENCHMARK(fib_tab) -> Iterations(1000); 

// Dynamic programming
long fib2(int n) {
    long f = 1, g = 0;
    while (n-- > 0) {g += f; f = g - f;}
    return g;
}

static void fib_dp(benchmark::State& state) {
    for (auto _: state) {
        long result;
        result = fib2(FIBTIME);
    }
}
BENCHMARK(fib_dp) -> Iterations(1000);

// Commi=on recurse
long fib3(int n) {
    if (n < 2)
        return n;
    else
        return fib3(n - 1) + fib3(n - 2); 
}
static void fib_com(benchmark::State& state) {
    for (auto _: state) {
        long result;
        result = fib3(FIBTIME);
    }
}
BENCHMARK(fib_com) -> Iterations(1000);

BENCHMARK_MAIN();
